1. Field of the Invention
This application relates to a method and apparatus for performing validation of elliptic curve public keys.
2. Description of the Prior Art
Cryptography is an essential tool in information security. It allows two correspondents to communicate secretly and/or authentically over a public channel. Private key systems require a secret to be shared beforehand by the correspondents. Such key distribution is often as difficult as the initial problem of secret communication, since the secret key must be transferred over a secure channel.
Public key cryptography helps solve the otherwise intractable problem of key distribution in cryptography. Without public key cryptography, the difficulty of key distribution is so high that securing information is impractical for all but those with the most extensive resources. Elliptic curve cryptography is a very efficient variety of public key cryptography, which is highly suitable for a wide variety of constrained environments. Other well-known varieties of public key cryptography include RSA and (ordinary) Diffie-Hellman.
Public key validation involves making sure that the public keys have the requisite properties, which ensures that no security compromises result from processing invalid public keys. For elliptic curve cryptography, some of the security compromises that can result from processing invalid public keys include small subgroup attacks and invalid-curve attacks.
Elliptic curve public key validation comes in two varieties, as set forth in the standards ANSI X9.62 and ANSI X9.63, namely partial validation and full validation. Elliptic curve public keys are elliptic curve points, and for a given set of elliptic curve domain parameters, a given point can be either valid or not valid. Elliptic curve domain parameters consist of a finite field size q together with a given representation FR of field elements, coefficients a and b of the elliptic curve equation, a prime number n, a cofactor h, and a base point or generator G. Suppose that Q is purported to be a valid elliptic curve point for domain parameters (q, FR, a, b, n, h, G). The point Q is fully valid if the following four conditions are met:
1. Q is not 0, the point at infinity (also known as the identity, zero or neutral element of the elliptic curve);
2. Q=(x, y) where x and y are valid elements of the finite field of size q for the given field representation FR;
3. E (x, y)=0, where E is given by the equation for the elliptic curve. For prime q>3, this means that y2=x3+ax+b, and for even q, this means that y2+xy=x3+ax2+b;
4. nQ=0, where, nQ means Q added n times to 0, called a scalar multiple of Q.
If the first three conditions hold, then Q is said to be partially valid.
The straightforward way to check condition 4 is to do scalar multiplication. However, scalar multiplication is a computationally intensive step of elliptic curve cryptography. The computation cost of typical operations in elliptic curve cryptography, such as signing, verifying, encrypting and decrypting, is roughly equal to somewhere between one to one-and-a-half scalar multiplications. Therefore, full validation, at least using the straightforward methods, roughly doubles the computational cost. In practice, therefore alternate techniques are used to thwart some of the attacks, such as small subgroup attacks, that full validation seeks to prevent.
Some elliptic curve cryptographic schemes use the so-called cofactor method. Here the public key Q is scalar multiplied by h before further use. Then n(hQ)=0, which prevents many types of small subgroup attacks. In such cases, partial validation of Q suffices to prevent these attacks. For the small h values typically used, such as 1,2 and 4, the cofactor method is much more efficient than the straightforward method of doing full validation, because computing hQ for small h is much faster than computing nQ since n is a large prime.
Another method is the so-called compatible cofactor method, which is first scalar multiplying Q by h, as above, getting a result hQ so that n(hQ)=0, and then scalar multiplying by h−1 mod n. If Q has order n to begin with, the result of these two steps is Q itself, and thus the term compatible. If Q does not have order n, the result of the operations has order n but is different from Q. Generally, the compatible cofactor method requires computing a full scalar multiplication so is no more efficient than the obvious method of doing full validation.
It should be noted that when the cofactor h=1, partial validation and full validation are equivalent. That is, when h=1 no extra steps are necessary beyond those in partial validation to accomplish full validation.
The known small subgroups attacks that full validation thwarts compromise log2(h) bits of elliptic curve private keys. There may, however, be more damaging attacks exploiting not fully validated elliptic curve points, which are as yet undiscovered. As a precaution, therefore, full validation is highly recommended, wherever possible. A common practice, however, has been to use partial validation. When partial validation is not supplemented by one of the alternate techniques above, such as the cofactor method, the known attacks reduce the security by log2(h)/2 bits, and the unknown attacks might reduce it by more.
It is an object of the present invention to obviate or mitigate some of the above disadvantages.